package com.xiaofu.sort.shell;

import com.xiaofu.sort.Sort;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: xiaofu
 * @DESCRIPTION: a technology seeker
 * @date: 2021-08-10 2:01
 */
public class ShellSort extends Sort {

    @Override
    protected void sort() {
        List<Integer> stepSequence = shellStepSequnce();
        for (Integer step : stepSequence) {
            sort(step);
        }
    }

    /**
     * 分成step列进行排序
     * @param step
     */
    private void sort(int step){
        // col: 第几列 colum的简称
        for (int col = 0; col < step; col++) { //对第col列进行排序
            //对[0,array.length)范围进行插入排序
            for (int begin = col + step; begin < array.length; begin = begin + step) {
                int cur = begin;
                while (cur > col && cmp(cur, cur - step) < 0) {
                    swap(cur, cur - step);
                    cur-=step;
                }
            }
        }
    }


    private List<Integer> shellStepSequnce(){
        List<Integer> stepSequence = new ArrayList<>();
        int step = array.length;
        while ((step = step >> 1) > 0){
            stepSequence.add(step);
        }
        return stepSequence;
    }
}
